The State of the Art in Visualizing Dynamic Graphs

  • 论文原文:The State of the Art in Visualizing Dynamic Graphs
  • 作者:Fabian Beck, Michael Burch, Stephan Diehl, and Daniel Weiskopf
  • 发表刊物/会议: Eurographics Conference on Visualization (EuroVis2014)

论文前半部分讲其如何收集数据,如何进行分类等等,就不再细述,直接从介绍方法开始。

有个表格比较有意思,这里展示一下:

类型 论文类型
application(应用) 讲动态图可视化方法应用于某个特定领域
evaluation(评估) 系统,理论地对可视化方法进行评估
technique(技术) 新颖的可视化技术或系统
时间表达方法
animation(动画) 利用动画来映射不同的时间
timeline(时间轴) 将时间映射到时间轴上的空间
generic(一般) being applicable to all representations of time
图的表达方法
node-link(节点链接) 用链接连起来的节点
matrix(矩阵) 邻接矩阵
generic(一般) being applicable to all graph representations
评估 评估的类型
algorithmic 用指标来算法性的评估表达方法
case_study 用一些应用案例来进行讨论
none 没有
user_study 通过其他用户来进行用户实验
expert 通过其他领域或者可视化专家来评价方法
survey 相关工作的调研
theoretical 证明或者是运行时间复杂度的理论考察
应用
biology bioinformatics data such as protein interactions or
metabolic pathways
business business- or economy-related data such as financial
transactions, stock market, business processes
document document collections, bibliometrics, and information re-
trieved from texts
eye_tracking data recorded during eye-tracking experiments
infrastructure infrastructure networks such as computer, communica-
tion, power, or road networks
media data related to movies, TV, music, news and the like
social social networks, social media, and other data from social
life
software_engineering information related software such as components, source
code, developers, documentation, etc.
sports sports-related data such as performance data or results
generic no specific application suggested

Animation(动画)

一般布局(General-Purpose Layout)

一般可以分为 online 和 offline 两种大类,online 的表示只考虑过去的 time step,来计算当前的布局;而 offline 则考虑了过去跟未来的,能够维持更好的 mental map。

Online Problem

一开始这个问题始于 交互,因为在进行交互的时候,过去的时间片段已知,而未来的时间片段仍然是未知的。

  • 【MISUE K., EADES P., LAI W., SUGIYAMA K.: Layout adjustment and the mental map. Journal of Visual Languages & Computing 6, 2 (1995), 183–210. 】:解决图编辑以及节点重叠的问题:让力引导算法要保持节点之间初始的垂直和水平位置的顺序。
  • 【BRANDES U., WAGNER D.: A Bayesian paradigm for dynamic graph layout. In Graph Drawing (1997), GD, Springer, pp. 236–247.】:用贝叶斯决策理论(Bayesian decision theory)来描述问题:在出初始布局上考虑可读性(readability model)以及考虑后面的布局与初始布局之间的差距,即稳定性(stability model)
  • 【LEE Y.-Y., LIN C.-C., YEN H.-C.: Mental map preserving graph drawing using simulated annealing. In Proceedings of the 2006 Asia-Pacific Symposium on Information Visualisation (2006), APVis, Australian Computer Society, Inc., pp. 179–188】:将这个问题考虑成一个优化问题,模拟退火算法,针对有权图。
  • 【GOROCHOWSKI T. E., DI BERNARDO M., GRIERSON C. S.: Using aging to visually uncover evolutionary processes on networks. IEEE Transactions on Visualization and Computer Graphics 18, 8 (2012), 1343–1352.】:引入节点年龄(node age)的概念来保持布局
  • 【FRISHMAN Y., TAL A.: Online dynamic graph drawing. IEEE Transactions on Visualization and Computer Graphics 14, 4 (2008), 727–740】利用了 GPU 进行了加速布局计算
  • HAYASHI A., MATSUBAYASHI T., HOSHIDE T., UCHIYAMA T.: Initial positioning method for online and real-time dynamic graph drawing of time varying data. In Proceedings of the 17th International Conference on Information Visualisation (2013), IV, pp. 435–444.】:调研了初始节点位置对布局算法的影响

Offline Problem

首先需要明白一个 super-graph 的概念,存在时间越长的边,会在 super-graph 中拥有更高的权重。

image-20181115111357623

  • 【DIEHL S., GÖRG C., KERREN A.: Preserving the mental map using foresighted layout. In Proceedings of the 3rd Joint Eurographics–IEEE TCVG Conference on Visualiza- tion (2001), VisSym, Eurographics Association, pp. 175–184.】:提出了 foresighted layout 算法,将不活跃的节点聚集在一起,然后再构建 super-graph。
  • 【DIEHL S., GÖRG C.: Graphs, they are changing – dynamic graph drawing for a sequence of graphs. In Graph Draw- ing, GD. Springer-Verlag, 2002, pp. 23–31.】:引入了 Tolerance 的概念,允许一定程度的偏移,可以为每一帧的布局继续用力引导做优化
  • 【ERTEN C., HARDING P. J., KOBOUROV S. G., WAMPLER K., YEE G.: GraphAEL: Graph animations with evolving layouts graph drawing. In Graph Drawing, GD. Springer, 2004, pp. 98–110.】:相同的节点用虚拟边相连,并忽略来自不同帧的相同节点之间的斥力。
  • 【BAUR M., SCHANK T.: Dynamic Graph Drawing in Visone. Tech. rep., Fakultät für Informatik, Universität Karlsruhe, 2008.】:引入了能量因子(energy factors)的概念,相同的节点之间的位置距离越远,能量越高,目标是最小化能量。
  • 【FENG K.-C., WANG C., SHEN H.-W., LEE T.-Y.: Coherent time-varying graph drawing with multifocus+context interaction. IEEE Transactions on Visualization and Computer Graphics 18, 8 (2012), 1330–1342.】:可以选择多个焦点,聚焦的焦点以及他们的邻域都会被放大。

Transition Problem

因为动画过程中,经常会在同一时间内发生太多的变化,用户难以追踪。

  • 【HUANG M. L., EADES P., WANG J.: On-line animated visualization of huge graphs using a modified spring algorithm. Journal of Visual Languages & Computing 9, 6 (1998), 623–645.】:当聚焦到一个节点上的时候,这个节点会被转到中间,然后节点再消失和出现。

  • 【FRIEDRICH C., EADES P.: The Marey graph animation tool demo. In Graph Drawing (2001), GD, Springer, pp. 396–406.】:将整个过程分成四个阶段:1. 需要消失节点和边消失掉;2. 布局进行转换;3. 单独的那些节点被转换到新的位置上;4. 新增节点和边

  • 【FRIEDRICH C., HOULE M. E.: Graph drawing in motion II. In Graph Drawing (2002), GD, Springer, pp. 220–231.】:对上述的工作进行了扩展,节点进行了聚类,然后再一起运动

  • 【NESBITT K. V., FRIEDRICH C.: Applying gestalt princi- ples to animated visualizations of network data. In Proceedings of the 6th International Conference on Information Visualisation (2002), IV, IEEE, pp. 737–743.】:推荐用 Gestalt laws 来捕获/组织运动过程

  • 【LOUBIER E., DOUSSET B.: Temporal and relational data representation by graph morphing. Safety and Reliability for Managing Risk 14, 02 (2008), 2008–16.】:(对不起没读懂,大概讲的是在变化为上一帧布局变换到下一帧的时候,先对齐到 super-graph,以维护 mental map)a super-graph layout is computed with nodes in the same time step attracted to a specific position; for the transition between two time steps, the graph is first morphed to the super-graph to recalibrate the mental map, before the super-graph is further transformed into the layout of the next time-step.

  • 【HURTER C., ERSOY O., FABRIKANT S., KLEIN T., TELEA A.: Bundled visualization of dynamic graph and trail data. IEEE Transactions on Visualization and Computer Graph- ics (2013).】:假如节点位置固定,则可以利用 edge bundling 的方法来展示边的变化。

    Nov-15-2018 15-09-00

  • 【BACH B., PIETRIGA E., FEKETE J.-D.: GraphDiaries: Animated transitions and temporal navigation for dynamic networks. IEEE Transactions on Visualization and Computer Graphics 20, 5 (2014), 740–754.】:类似上面的,但是会高亮那些移除的活着新增的元素。

    Nov-15-2018 15-24-12

特殊目的布局(special-purpose layout)

Compound Graph(复合图)

动态复合图的布局,需要在不同时刻追踪聚类,不仅要保持布局稳定,也要保持聚类的稳定。

  • 【FRISHMAN Y., TAL A.: Dynamic drawing of clustered graphs. In Proceedings of the 2004 IEEE Symposium on Infor- mation Visualization (2004), InfoVis, IEEE, pp. 191–198.】:一种 online 的方法,在聚类外面绘制盒子,保证节点在该范围内。(下图上面是不加该方法的布局,下图是加入了文章的方法)

    image-20181115153232857

  • 【[KG06] KUMAR G., GARLAND M.: Visual exploration of com- plex time-varying graphs. IEEE Transactions on Visualization and Computer Graphics 12, 5 (2006), 805–812.】:针对 3D 图,画上气泡来表达复合的结构。

    image-20181115153635432

  • 【POHL M., BIRKE P.: Interactive exploration of large dynamic networks. In Proceedings of the 10th Inter- national Conference on Visual Information Systems (2008), VISUAL, Springer-Verlag, pp. 56–67.】:是对 foresighted layout 的一种扩展,做了一个个嵌套的盒子。

    image-20181115155535509

  • 【REITZ F., POHL M., DIEHL S.: Focused animation of dynamic compound digraphs. In Proceedings of the 13th Interna- tional Conference on Information Visualisation (2009), IV, IEEE Computer Society, pp. 679–684】:利用层次结构,折叠不变的结构,使得动画更加清楚。

  • 【LIN Y.-R., SUN J., CAO N., LIU S.: ContexTour: Contextual contour visual analysis on dynamic multi-relational clustering. In Proceedings of the 2010 SIAM International Con- ference on Data Mining (2010), SDM, pp. 418–429.】:用不同颜色的 contour map 来表示不同的聚类。

    image-20181115161137542

  • 【MASHIMA D., KOBOUROV S., HU Y.: Visualizing dynamic data with maps. IEEE Transactions on Visualization and Computer Graphics 18, 9 (2012), 1424–1437.】【HU Y., KOBOUROV S. G., VEERAMONI S.: Embed- ding, clustering and coloring for dynamic maps. In Proceedings of the 2012 IEEE Pacific Visualization Symposium (2012), Paci- ficVis, IEEE Computer Society, pp. 33–40.】:是对上述算法的拓展,用空间填充的方法来绘制。

    image-20181115161453296

  • 【ABELLO J., HADLAK S., SCHUMANN H., SCHULZ H.-J.: A modular degree-of-interest specification for the vi- sual analysis of large dynamic networks. IEEE Transactions on Visualization and Computer Graphics 20, 3 (2013), 337–350.】:当用户分析图的某一部分的细节时,利用 DOI 方法对其他部分进行聚类。

    image-20181115161728559

Other

针对 planar graph 和 acyclic graph,不再细述。


Timeline(时间到空间的映射)

能提供整体的视角,但因为每个图的空间都缩小了,会降低可读性。在这种方法下,scalability 时主要挑战。

Juxtaposed(并列)

存在的问题:

  1. 相邻两帧之间差距不大,不便观察
  2. 难以追踪某个特定节点
  3. 每幅图都太小,以至于会有杂乱

image-20181115173957261

  • 【GREILICH M., BURCH M., DIEHL S.: Visualizing the evolution of compound digraphs with TimeArcTrees. Computer Graphics Forum 28, 3 (2009), 975–982.】:将节点摆放在水平线上,以便追踪,但可读性比较差,如上图最左边。
  • 【BURCH M., VEHLOW C., BECK F., DIEHL S., WEISKOPF D.: Parallel Edge Splatting for scalable dynamic graph visualization. IEEE Transactions on Visualization and Computer Graphics 17, 12 (2011), 2344–2353.】:提出了一种新方法:Parallel Edge Splatting,如 上图中间,它将垂直排列的图人为的分成二部图,这个二部图中边的方向都是从左向右的。
  • 【BURCH M., BECK F., WEISKOPF D.: Radial Edge Splatting for visualizing dynamic directed graphs. In Proceed- ings of the 4th International Conference on Information Visu- alization Theory and Applications (2012), IVAPP, SciTePress, pp. 603–612】:是对 Parallel Edge Splatting 的一种圆形的拓展。
  • 【BURCH M., FRITZ M., BECK F., DIEHL S.: Time- SpiderTrees: A novel visual metaphor for dynamic compound graphs. In Proceedings of the IEEE Symposium on Visual Lan- guages and Human-Centric Computing (2010), VL/HCC, IEEE, pp. 168–175.】:将 node-link 方法转换到嵌套的圆形中,如上图右边,但并不会画出所有的边,只会画一部分。
  • 【FARRUGIA M., HURLEY N., QUIGLEY A.: Exploring temporal ego networks using small multiples and tree-ring layouts. In Proceedings of the 4th International Conference on Ad- vances in Computer-Human Interactions (2011), ACHI, pp. 79– 88.】使用了一种相似的布局方法来表达 ego-centered 的动态图

Superimposed(重叠的)

重叠的画法,需要节点在相同的位置,并且不同时间的边应该有不同的样式。将多个 2D 的图堆叠起来就会形成 3D,但这些堆叠的图层是离散的,故而只能说成是 2.5D。

  • 【DWYER T., EADES P.: Visualising a fund manager flow graph with columns and worms. In Proceedings of the 6th In- ternational Conference on Information Visualisation (2002), IV, IEEE, pp. 147–152.】:在不可见的 2D 平面上放置 3D 圆柱体。

    image-20181116091643871

  • 【BRANDES U., CORMAN S. R.: Visual unrolling of network evolution and the analysis of dynamic discourse. In- formation Visualization 2, 1 (2003), 40–50.】:跟上者类似,放置 3D 的圆柱体代表节点,用一些半透明的平面来表达图层,下图左。

    image-20181116091729780

  • 【ERTEN C., KOBOUROV S. G., LE V., NAVABI A.: Si- multaneous graph drawing: Layout algorithms and visualization schemes. In Graph Drawing (2004), GD, Springer, pp. 437–449.】:如上图右,允许节点有不同的位置,他们使用了一种改进的李引导算法,使得节点大致保持同一位置,以保留 mental map。

  • 【GROH G., HANSTEIN H., WÖRNDL W.: Interactively visualizing dynamic social networks with DySoN. In Proceedings of the 2009 Workshop on Visual Interfaces to the Social and the Semantic Web (2009), VISSW.】:拓展上述方法,将上图右边的虚拟的虚线,以管状进行绘制。

    image-20181116100226178

Integrated(集成)

在集成图里面,时间轴会被加入到节点链接图里面,那么,在不破坏布局的情况下,不同时间片段的图就不可能被单独抽离。

image-20181116103251163

  • 【REITZ F.: A framework for an ego-centered and time-aware visualization of relations in arbitrary data reposito- ries. arXiv preprint arXiv:1009.5183 (2010).】:在 ego networks 上,将时间轴编码到边上,边的权重演变被编码成分段的颜色,故而每条边都是一个独立的时间轴,上图左。
  • 【SHI L., WANG C., WEN Z.: Dynamic network visualization in 1.5D. In Proceedings of the 2011 IEEE Pa- cific Visualization Symposium (2011), PacificVis, pp. 179–186.】:针对 ego network,将中心节点变成时间轴,每当新的边出现的时候,将它们按照时间书序依次连接到中心的时间轴上,上图中。
  • 【VAN DEN ELZEN S., HOLTEN D., BLAAS J., VAN WIJK J.: Dynamic network visualization with extended massive sequence views. IEEE Transactions on Visualization and Computer Graphics (2013).】:针对边代表瞬时事件的图(也即这些事件并不会持续一段时间),提出 Extended Massive Sequence Views,事件被绘制在水平线上,节点则被排列在垂直线上,如上图右。

基于矩阵的方法(Matrix-Based)

单元内部的时间轴(Intra-Cell Timelines)

每一个单元格都会抱憾一条独立的时间轴。有很多不同的时间轴表达方法,如下图所示。

image-20181116131911711

  • 【BURCH M., SCHMIDT B., WEISKOPF D.: A matrix-based visualization for exploring dynamic compound digraphs. In Proceedings of the 17th International Conference Information Visualisation (2013), IV, IEEE, pp. 66–73.】&【YI J. S., ELMQVIST N., LEE S.: TimeMatrix: Analyzing temporal social networks using interactive matrix-based visualizations. International Journal of Human-Computer In- teraction 26, 11-12 (2010), 1031–1051.】:直接放置了一条水平的 bar chart,如上图左。

  • 【BURCH M., SCHMIDT B., WEISKOPF D.: A matrix-based visualization for exploring dynamic compound digraphs. In Proceedings of the 17th International Conference Information Visualisation (2013), IV, IEEE, pp. 66–73.】:在矩阵边上放置层次结构,从而来表达一个动态的复合图。

    image-20181116132732275

  • 【YI J. S., ELMQVIST N., LEE S.: TimeMatrix: Analyzing temporal social networks using interactive matrix-based visualizations. International Journal of Human-Computer In- teraction 26, 11-12 (2010), 1031–1051.】:节点是聚合后的时间轴,不同的边类型就用不同的颜色进行编码。

  • 【BRANDES U., NICK B.: Asymmetric relations in longitudinal social networks. IEEE Transactions on Visualization and Computer Graphics 17, 12 (2011), 2283–2290.】:利用叫做 Gestaltlines 的表达方法,使用了堆叠的线条,线条的角度,左面长度和右面长度可以来编码三种不同的指标,如上上图的中间部分。

  • 【STEIN K., WEGENER R., SCHLIEDER C.: Pixel-oriented visualization of change in social networks. In Proceedings of the 2010 International Conference on Advances in So- cial Networks Analysis and Mining (2010), ASONAM, IEEE, pp. 233–240.】:建议了一种 pixel-based 的方法(基于像素图),将时间轴折叠成为像素图。每一个像素(或者说一个单元)表达时间上的一个点,用来编码当前时间片段的边的权重。文章还提到了几种折叠时间轴的方法:row-by-row, column-by-column, diagonal, etc.

    image-20181116134654857

分层矩阵(Layered Matrixed)

image-20181116134937923

  • 【BURCH M., DIEHL S.: TimeRadarTrees: Visualizing dynamic compound digraphs. Computer Graphics Forum 27, 3 (2008), 823–830.】&【BURCH M., HÖFERLIN M., WEISKOPF D.: Layered TimeRadarTrees. In Proceedings of the 15th International Conference on Information Visualisation (2011), IV, IEEE, pp. 18– 25.】:将边和边之间的关系以环形编码到圆上,如下图左边的大圆,红色部分表示有边链接到该节点,小圆则表示有边从该节点出去。圆形的径向则是时间轴,也即上图第二图所示(radially distributtd)

    image-20181116141532045

  • 【VEHLOW C., BURCH M., SCHMAUDER H., WEISKOPF D.: Radial layered matrix visualization of dynamic graphs. In Proceedings of the 17th International Conference Information Visualisation (2013), IV, pp. 51–58.】:弯折矩阵变成圆环,每一个圆环都代表一个时刻,上上图 radially layered。

  • 【BACH B., PIETRIGA E., FEKETE J.-D.: Visualizing dynamic networks with matrix cubes. In Procceedings of the SICCHI Conference on Human Factors in Computing Systems (2014), CHI.】将 2D 的图堆叠成 3D 的,上上图 stacked。

Hybrid (Animation, Timeline)(对动画跟时间轴的混合)

  • 【HADLAK S., SCHULZ H.-J., SCHUMANN H.: In situ exploration of large dynamic networks. IEEE Transactions on Visualization and Computer Graphics 17, 12 (2011), 2334–2343.】:将一些小的可视化集成到更大的可视化中,通过这样的方法可以将动画集成到时间轴中;
  • 【SALLABERRY A., MUELDER C., MA K.-L.: Clustering, visualizing, and navigating for large dynamic graphs. In Graph Drawing (2012), GD, pp. 487–498.】:使用了一种基于时间轴的,但是也同样集成了通过节点链接图来表示的聚类演化动画。
  • 【BECK F., BURCH M., VEHLOW C., DIEHL S., WEISKOPF D.: Rapid serial visual presentation in dynamic graph visualization. In Proceedings of the 2012 IEEE Sym- posium on Visual Languages and Human-Centric Comput- ing (2012), VL/HCC, IEEE, pp. 185–192.】:将很长序列的图利用 Parallel Edge Splatting 的技术,通过移动时间轴来演示动画。
  • 【RUFIANGE S., MCGUFFIN M. J.: DiffAni: Visualizing dynamic graphs with a hybrid of difference maps and animation. IEEE Transactions on Visualization and Computer Graphics 19, 12 (2013), 2556–2565. 】:能够让用户将一部分时间轴集成为动画。

Research Challenges

在文章最后,作者讲了一些 reseach challenges,对寻找科研问题比较有帮助,可以列举一下(不再细述 evaluation 部分)

  • Visual Scalability:增加需要展示的数据,却仍要保留可读性,考虑三个维度,节点数量,边的密度以及时间。
  • Hybrids:混合 animation 跟 timeline,在静态图中已经很好的混合了节点链接跟矩阵。
  • Extended Data Dimensions:静态图变到动态图是加入了时间这个维度,那么在其他场景下, 是否还能加入其他的维度。已经有的是加入节点的层次关系,形成复合图。值得被研究的内容还有:动态的多属性图,带有不确定信息的动态图,有地理位置的图。
  • Interaction:navigation(导航),这个工作已经很多年没有人聚焦。在动态图中,用户不仅要在空间中进行导航,也需要在时间上进行导航。当然交互也可以用来集成多个模型(DiffAni)或者用来过滤数据。标注/编辑动态图都未进行研究。
  • Application:文学作品中的人物分析,金融和生物医药传染网络,眼部追踪数据。